Currently, there is a growing trend to make Asynchronous Transfer Mode (ATM) networking technology the base of future global communications. ATM has already been adopted as a standard for broadband communications by the International Telecommunications Union (ITU) and by the ATM Forum, a networking industry consortium.
As part of the ongoing enhancement to the ATM standard by work within the ATM Forum and other groups, the Private Network to Network Interface (PNNI) protocol has been developed for use between private ATM switches and between groups of private ATM switches. The PNNI specification includes two categories of protocols. The first protocol is defined for the distribution of topology information between switches and clusters of switches where the information is used to compute routing paths within the network. The main feature of the PNNI hierarchy mechanism is its ability to automatically configure itself within the networks in which the address structure reflects the topology. The PNNI topology and routing techniques are based on the well known link state routing technique.
The second protocol is effective for signaling, i.e., the message flows used to establish point-to-point and point-to-multipoint connections across the ATM network. This protocol is based on the ATM Forum User to Network Interface (UNI) signaling with mechanisms added to support source routing, crankback and alternate routing of source SETUP requests in the case of bad connections.
A high level block diagram illustrating the switching system reference model that the PNNI protocol is based on as shown in FIG. 1. The switching system, generally referenced 100, comprises a topology database 104 which interfaces with a topology data exchange module 106 within a route determination module 102. The topology data exchange module 106 communicates with neighboring nodes through a topology protocol. In addition, the switching system 100 communicates with a management entity via a management interface protocol. The switching system 100 also comprises a call processing module 124, a UNI signaling module 122 which communicates via a UNI signaling protocol, and a NNI signaling module 126 which communicates via a NNI signaling protocol. In addition, the call processing module 124 interfaces to a switching fabric 130 which provides the switching functionality for the cell stream that is input and output to and from the switching 100 system.
The PNNI hierarchy begins at the lowest level where the lowest level nodes are organized into peer groups. A logical node in the context of the lowest hierarchy level is the lowest level node. A logical node is typically denoted as simply a node. A peer group is a collection of logical nodes wherein each node within the group exchanges information with the other members of the group such that all members maintain an identical view of the group. When a logical length becomes operational, the nodes attached to it initiate and exchange information via a well known Virtual Channel Connection (VCC) used as a PNNI Routing Control Channel (RCC).
Hello message are sent periodically by each node on this link. In this fashion the Hello protocol makes the two neighboring nodes known to each other. Each node exchanges Hello packets with its immediate neighbors to determine its neighbor's local state information. The state information includes the identity and peer group membership of the node's immediate neighbors and a status of its links to its neighbors. Each node then bundles its state information in one or more PNNI Topology State Elements (PTSEs) which are subsequently flooded throughout the peer group.
PTSEs are the smallest collection of PNNI routing information that is flooded as a unit among all logical nodes within a peer group. A node topology database consists of a collection of all PTSEs received, which represent that particular node's present view of the PNNI routing topology. In particular, the topology database provides all the information required to compute a route from the given source node to any destination address reachable in or through that routing domain.
When neighboring nodes at either end of a logical length begin initializing through the exchange of Hellos, they may conclude that they are in the same peer group. If it is concluded that they are in the same peer group, they proceed to synchronize their topology databases. Database synchronization includes the exchange of information between neighboring nodes resulting in the two nodes having identical topology databases. A topology database includes detailed topology information about the peer group in which the logical node resides in addition to more abstract topology information representing the remainder of the PNNI routing domain.
During a topology database synchronization, the nodes in question first exchange PTSE header information, i.e., they advertise the presence of PTSEs in their respective topology databases. When a node receives PTSE header information that advertises a more recent PTSE version than the one that it has already or advertises a PTSE that it does not yet have, it requests the advertised PTSE and updates its topology database with the subsequently received PTSE. If the newly initialized node connects to a peer group then the ensuing database synchronization reduces to a one way topology database copy. A link is advertised by a PTSE transmission only after the database synchronization between the respective neighboring nodes has successfully completed. In this fashion, the link state parameters are distributed to all topology databases in the peer group.
Flooding is the mechanism used for advertising links whereby PTSEs are reliably propagated node by node throughout a peer group. Flooding ensures that all nodes in a peer group maintain identical topology databases. A short description of the flooding procedure follows. PTSEs are encapsulated within PNNI Topology State Packets (PTSPs) for transmission. When a PTSP is received its component PTSEs are examined. Each PTSE is acknowledge by encapsulating information from its PTSE header within the acknowledgment packet which is sent back to the sending neighbor. If the PTSE is new or of more recent origin then the node's current copy, the PTSE is installed in the topology database and flooded to all neighboring nodes except the one from which the PTSE was received. A PTSE sent to a neighbor is periodically retransmitted until acknowledged.
Note that flooding is an ongoing activity wherein each node issues PTSPs with PTSEs that contain updated information. The PTSEs contain the topology databases and are subject to aging and get removed after a predefined duration if they are not refreshed by a new incoming PTSE. Only the node that originated a particular PTSE can re-originate that PTSE. PTSEs are reissued both periodically and on an event driven basis.
A diagram illustrating the neighboring peer state machine describing the state of ongoing database synchronization and flooding with a neighboring node is shown in FIG. 2. As described previously, when a node first learns about the existence of a neighboring peer node which resides in the same peer group, it initiates the database exchange process in order to synchronize its topology database with that of its neighbors. The database exchange process involves exchanging a sequence of database summary packets which contain the identifying information of all PTSEs in a node topology database. The database summary packet performs an exchange utilizing a lock step mechanism whereby one side sends a database summary packet and the other side responds with its own database summary packet, thus acknowledging the received packet.
When a node receives a database summary packet from its neighboring peer, it first examines its topology database for the presence of each PTSE described within the packet. If the particular PTSE is not found in its topology database or if the neighboring peer has a more recent version of the PTSE then the node requests the PTSE from the particular neighboring peer or optionally from another neighboring peer whose database summary indicates that it has the most recent version of the PTSE.
The conversation that occurs between two peers for purposes of database synchronization and flooding is described by the neighboring peer state machine shown in FIG. 2. A corresponding neighboring peer data structure is maintained by the nodes located on either side of the link. The neighboring peer data structure includes information required to maintain database synchronization and flooding to neighboring peers.
With reference to FIG. 2, it is assumed that both nodes on either side of the link begin in the Neighboring Peer Down state 140. This is the initial state of the neighboring peer for this particular state machine. This state indicates that there are no active links through the neighboring peer. In this state, there are no adjacencies associated with the neighboring peer either. When the link reaches the point in the Hello protocol where both nodes are able to communicate with each other, the event AddPort is triggered in the corresponding neighboring peer state machine. Similarly when a link falls out of communication with both noes the even DropPort is triggered in the corresponding neighboring peer state machine. The database exchange process commences with the event AddPort which is thus triggered but only after the first link between the two neighboring peers is up. When the DropPort event for the last link between the neighboring peers occurs, the neighboring peer state machine will internally generate the DropPort last event closing all state information for the neighboring peers to be cleared.
It is while in the Negotiating state 142 that the first step is taken in creating an adjacency between two neighboring peer nodes. During this step it is decided which node is the master, which is the slave and it is also in this state that an initial Database Summary (DS) sequence number is decided upon. Once the negotiation has been completed, the Exchanging state 144 is entered. In this state the node describes is topology database to the neighboring peer by sending it database summary packets to it.
After the peer processes the database summary packets, the missing or updated PTSEs can then be requested. In the Exchange state 144 the database summary packets contain summaries of the topology state information contained in the node's database. In the case of logical group nodes, those portions of the topology database that where originated or received at the level of the logical group node or at higher levels are included in the database summary. The PTSP and PTSE header information of each such PTSE is listed is listed in one of the nodes database packets. PTSEs for which new instances are received after the exchanging status have been entered may not be included in any database summary packet since they will be handled by the normal flooding procedures.
The incoming data base summary packet on the receive side is associated with a neighboring peer via the interface over which it was received. Each database summary packet has a database summary sequence number that is implicitly acknowledged. For each PTSE listed, the node looks up the PTSE in its database to see whether it also has an instance of that particular PTSE. If it does not or if the database copy is less recent, then the node either re-originates the newer instance of the PTSE or flushes the PTSE from the routing domain after installing it in the topology database with a remaining lifetime set accordingly.
Alternatively, if the listed PTSE has expired, the PTSP and PTSE header contents in the PTSE summary are accepted as a newer or updated PTSE with empty contents. If the PTSE is not found in the node's topology database, the particular PTSE is put on the PTSE request list so it can be requested from a neighboring peer via one or more PTSE request packets.
If the PTSE request list from a node is empty, the database synchronization is considered complete and the node moves to the Full state 148.
However, if the PTSE request list is not empty then the Loading state 146 is entered once the node's last database summary packet has been sent but the PTSE request list is not empty. At this point, the node now knows which PTSE needs to be requested. The PTSE request list contains a list of those PTSEs that need to be obtained in order to synchronize that particular node's topology database with the neighboring peer's topology database. To request these PTSEs, the node sends the PTSE request packet which contains one or more entries from the PTSE request list. The PTSE request list packets are only sent during the Exchange state 144 and the Loading state 146. The node can send a PTSE request packet to a neighboring peer and optionally to any other neighboring peers that are also in either the Exchanging state or the Loading state and whose database summary indicate that they have the missing PTSEs.
The received PTSE request packets specify a list of PTSEs that the neighboring peer wishes to receive. For each PTSE specified in the PTSE request packet, its instance is looked up in the node's topology database. The requested PTSEs are subsequently bundled into PTSPs and transmitted to the neighboring peer. Once the last PTSE and the PTSE request list has been received, the node moves from the Loading state 146 to the Full state 148. Once the Full state has been reached, the node has received all PTSEs known to be available from its neighboring peer and links to the neighboring peer can now be advertised within PTSEs.
A diagram illustrating a PNNI topology state packet (PTSP) comprising a plurality of PNNI topology state elements (PTSEs) is shown in FIG. 3. A PTSP is made up of one or more PTSEs sequentially placed one after another as shown in FIG. 3 labeled PTSE #1, PTSE #2 all the way through the final PTSE labeled PTSE #N.
However, a potential problem may arise during the operation of a PNNI protocol based ATM network. Since each node in the PNNI based ATM network holds the entire topology of the network, including that of its peer and hierarchies, if the network grows beyond a certain size the particular node can potentially run out of memory in which to hold the topology information. This is a problem since all the nodes in the network are constructed with a finite amount of memory. This memory is used to store and forward all the PTSEs received from neighboring nodes. If a node exhausts its memory either more memory must be added, i.e., the node upgraded, or the node must be taken out of operation and upgraded with a new node containing more memory.
Once a node determines that it has run out of memory, it is defined to be in an overload state, meaning it lacks sufficient RAM for storing additional topology database information. A node in an overload state has limited switching capability and route calculations may or may not be possible. Even if routing is possible, it is not permitted in accordance with the PNNI-1 specifications. This is because it is not desirable to have a non-optimum route calculated due to the node's memory containing only a partial topology database thus making any route calculations potentially non-optimal. However, the node can function as a transit node which means it can function as a hop along the route for another node's routing list.
An overloaded node is a node that is in the overload state and, as mentioned above, cannot perform routing with the exception of local routing over direct connections to its local users. In response to entering the overload state, such a node generates and floods a PTSE which identifies itself as being in the overload state.
The prior art attempts to solve this problem include forcing the node in an overload state to advertise its condition to all other nodes, i.e., that the node is in the overload state. The node is also not permitted to function as a source node in calculating a source routing list for a path through the network to a non-local destination. The node is, however, permitted to function as a source node for routes that are local, i.e., connections to local users. In addition, in order to be removed from the overload state, the node must either be replaced with a node having more memory or modified so as to have additional memory installed in it.
Several problems exist with the prior art solutions described above. One, it is not always a simple procedure to replace or add memory to a node that already exists in the network. Such modifications typically are time consuming and thus entail taking a node down, i.e., out of service, for a certain time period. In addition, it is difficult and costly to replace switches that have been placed in operation most likely several years ago and which were constructed with less memory.
A problem arises when a node in an overload state receives a source routing request from a source user connected to the node. Since the node is in an overload state, it has only partial knowledge of the topology of the network. Although permitted, it is not preferably for a node in the overload state to perform routing functions for non-local destinations. Performing routing is not recommended because the routes a node in an overload state calculates using a partial topology database are likely to be suboptimal. This is in accordance with the current PNNI-1 standard. Only local routing may be performed by a node in the overload state.
In addition, when determining a route, a node in an overload state may not find a route to a particular destination even though a route exists in reality. This can occur when a user is connected to a node that is not in the topology database of the node in the overload state.